package graph.question;

import graph.GraphNode;
import graph.graphtype.NoDirectGraph;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @Description
 * @Author 26233
 * @Create 2021-04-11 15:52:58
 */

public class Dfs {

    public List<Integer> dfs(NoDirectGraph g, int id){

        int[] visited = new int[g.table.length];
        List<Integer> result = new ArrayList<>();

        GraphNode tempNode = g.table[id];
        Stack<GraphNode> stack = new Stack<>();

        stack.add(tempNode);

        while (!stack.isEmpty()){
            tempNode = stack.pop();

            if (visited[tempNode.id] == 1) continue;

            visited[tempNode.id] = 1;
            result.add((Integer)tempNode.data);

            if (result.size() == g.table.length) break;

            tempNode = tempNode.next;
            while(tempNode != null){
                stack.add(tempNode.edgeNode);// 放table[i] 的值
                tempNode = tempNode.next;
            }

        }
        return result;
    }

    public void dfs(NoDirectGraph g, int id, List<Integer> result, int[] visited){

        GraphNode tempNode = g.table[id];
        if (result.size() == g.table.length) return;
        result.add(id);
        visited[id] = 1;
        while (tempNode.next != null){
            if (visited[tempNode.next.id] == 1){
                tempNode = tempNode.next;
                continue;
            }
            tempNode = tempNode.next;
            dfs(g, tempNode.id, result, visited);
        }
    }

    public static void main(String[] args) {
        int[][] edges = new int[][]{{0, 1}, {0, 2}, {0, 4}, {1, 0}, {1, 3}, {2, 0}, {2, 3}, {2, 4}, {3, 1}, {3, 2}, {3, 4}, {4, 0}, {4, 2}, {4, 3}};
        int[] data = new int[]{1, 2, 3, 4, 5};

        NoDirectGraph g = new NoDirectGraph(data.length, data);
        g.generateGraph(edges);

        List<Integer> result = new ArrayList<>();
        int[] visited = new int[data.length];

        new Dfs().dfs(g, 0, result, visited);

        System.out.println("result = " + result);



    }
}
